Most compilers perform optimizations on a source program in order to produce object code that executes faster and which consumes minimal memory space. SSA is an intermediate representation of a source program that is typically used during the optimization phase of a compiler. The SSA form requires each program variable to be defined only once. This form is simpler and efficient for use in several optimizations, such as register promotion, loop unrolling, code motion, constant propagation, dead code elimination, partial redundancy elimination, and the like.
FIG. 1A illustrates a control flow graph 100 depicting the intermediate representation of a source program. The variable, x, is defined in nodes 102, 104 and used in nodes 106, 108. A definition is an instruction that assigns a value to a variable (e.g., "x=") and a use is an instruction that uses the value assigned to the variable (e.g., "=x"). Since the variable, x, is defined more than once, the intermediate representation is not in SSA form.
In order to represent a source program in SSA form, a variable is represented by one or more cloned variable names. A phi-function (.PHI.-function) is used at join points to define a cloned variable name that represents the definitions of the variable and the associated cloned variable name definitions that can reach the join point.
FIG. 1B shows the control graph 100 in SSA form. There are multiple cloned variable names representing x: a first cloned variable name, x.sub.1, is defined in node 102 and is used in nodes 106, 108; a second cloned variable name, x.sub.2, is defined in node 104 and used in node 108; and a third cloned variable name, x.sub.3, is defined and used in node 108. The phi-function (.PHI.(x.sub.1,x.sub.2)) in join node 108 is used to indicate the definitions of x that reach the join node 108. The cloned variable name x.sub.3 is assigned the definition that reaches the join node 108, which in this case can be either x.sub.i or x.sub.2. The multiple cloned variable names x.sub.1, x.sub.2, x.sub.3 are used to conform the intermediate representation to SSA form. The variable x is replaced by the multiple cloned variable names, x.sub.1, x.sub.2, x.sub.3, each of which is defined only once thereby satisfying the SSA form.
A compiler can perform one or more optimization phases where each optimization phase can leave the intermediate representation in non-SSA form. The task of reconstructing the entire program into the SSA form after each optimization phase is time consuming and expensive. For this reason, incremental SSA update techniques have been proposed. The incremental SSA update techniques reconstruct portions of a program that were affected by a particular optimization technique into SSA form after the optimization occurs. The incremental SSA update techniques avoid reconstructing the entire program after each optimization is performed. However, the incremental SSA update techniques need to be efficient in order to be practical for commercial implementations.